package 每日一题;

import java.util.Random;

public class Solution {
    //蓄水池抽样算法
    ListNode head;
    Random random;
    public Solution(ListNode head) {
       this.head = head;
       random = new Random();
    }
    public int getRandom() {
        int i = 1,ans = 0;
        for (ListNode node = head;node!=null;node = node.next){
            if (random.nextInt(i)==0){
                ans = node.val;
            }
            i++;
        }
        return ans;
    }
}
